# coding: utf-8

# 作者：雪山凌狐
# 代码复现：动态规划问题-切分钢管卖钱，看怎么切卖得最多

from collections import defaultdict
from functools import lru_cache

# 所有钢管米数从小到大的价格
prices = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 33]
# 设定字典里面的默认值，当访问字典中的键不存在时，返回默认值，int 的默认值为 0
# 因为我们总共只有 11 种钢管，当需要看 12 米长的钢管价钱时，会返回 0
complete_price = defaultdict(int)
# enumerate 会返回列表的迭代器，第一个元素为索引，第二个元素为列表的值
for i, p in enumerate(prices):
    # 将米数作为键，将钱数作为值
    complete_price[i + 1] = p

# 将对应米数的最佳切法（能卖的钱最多）存起来
solution = {}

# lru_cache 装饰器可以静态缓存之前计算的结果值，可以使用 maxsize 指定存储最近最常使用的指定数量的结果值
# 后续可以直接从缓存调用，无需再算一遍（如果不这样弄，重复运算，当 n 很大时运算时间会非常非常长）
@lru_cache(maxsize=2**10)
def r(n):
    """
    计算指定米数钢管最多能卖多少钱的函数（可切分）
    n 指的是米数
    """

    # 可能的算钱方案有两种
    # 方法一：钢管完全不切，为 complete_price[n]，(n, 0) 为切法
    # 方法二：另一种方法就是做切割，比如切成两段左边那一段长度为 i，右边那一段长度就为 n - i
    # 而这种两段切法有 range(1, n) 种可能性，需要分别都计算这些的结果，同样第二个元素为切法
    # 为什么不是三段、四段呢？我们其实已经考虑了这种情况。看 r(i) + r(n - i)，这部分是递归函数
    # 每部分递归里面又进行了两两切割求最优解，所以其实是把每一种切割情况的树都遍历考虑了的
    candidates = [(complete_price[n], (n, 0))] + \
                  [(r(i) + r(n - i), (i, n - i)) for i in range(1, n)]

    # 获取价钱最大值，虽然 candidates 里有两个元素，但会按照第一个元素来获取最大值，split 是分割方法
    optimal_price, split = max(candidates)

    # 将这个米数的最优分割方法加入解决方案中
    solution[n] = split

    return optimal_price

def parse_solution(n, cut_solution):
    """
    解析展示每个米数最佳的切分方案
    n 为米数
    cut_solution 为解决方案，必须要运行完 r 这个函数才有该结果
    """

    # 解决方案存的是二分切割法的最优解，如果需要明细，需要递归获取明细的切分方法
    left, right = cut_solution[n]

    # 当左边的钢管或右边的钢管长度为 0 的时候，说明，不切分已经是最优解了，不用再去获取切分后的值了
    if left == 0 or right == 0:
        return [left + right]
    # 否则，就通过递归的方式去解析左边和右边钢管具体怎么切分
    else:
        return parse_solution(left, cut_solution) + parse_solution(right, cut_solution)

if __name__ == '__main__':
    length = 103
    print(f"米数为{length}的钢管能卖的最大价钱为：")
    print(r(length))
    print("对应的钢管长度切分方法为：")
    print(parse_solution(length, solution))